import java.math.BigInteger;

/*
 * @lc app=leetcode.cn id=67 lang=java
 *
 * [67] 二进制求和
 *
 * https://leetcode-cn.com/problems/add-binary/description/
 *
 * algorithms
 * Easy (46.00%)
 * Total Accepted:    15.5K
 * Total Submissions: 33.6K
 * Testcase Example:  '"11"\n"1"'
 *
 * 给定两个二进制字符串，返回他们的和（用二进制表示）。
 * 
 * 输入为非空字符串且只包含数字 1 和 0。
 * 
 * 示例 1:
 * 
 * 输入: a = "11", b = "1"
 * 输出: "100"
 * 
 * 示例 2:
 * 
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 * 
 */
class Solution {

    private static final int ONE_ZERO_ASNI_VALUE = '0';
    private static final int TWO_ZERO_ASNI_VALUE = '0' + '0';

    public String addBinary(String a, String b) {
        if (a.length() < b.length()) {
            return addBinary(b, a);
        }
        StringBuilder sb = new StringBuilder();
        char[] aChars = a.toCharArray();
        char[] bChars = b.toCharArray();
        int carry = 0;
        int ai = aChars.length - 1;
        int bi = bChars.length - 1;
        for (; bi >= 0; --ai, --bi) {
            int res = aChars[ai] + bChars[bi] + carry - TWO_ZERO_ASNI_VALUE;
            carry = res >> 1;
            sb.append(res & 1);
        }
        for (; ai >= 0; --ai) {
            int res = aChars[ai] + carry - ONE_ZERO_ASNI_VALUE;
            carry = res >> 1;
            sb.append(res & 1);
        }
        if (carry == 1) {
            sb.append(1);
        }
        return sb.reverse().toString();
    }
}
